package main

import (
	"fmt"
)

type LinkedList struct {
	Head *Node
	Tail *Node
}
type Node struct {
	Data interface{}
	Next *Node
}

func NewNode(d interface{}, next *Node) *Node {
	n := &Node{Data: d, Next: next}
	return n
}

func (l *LinkedList) InsertAtHead(data interface{}) {
	n := NewNode(data, l.Head)
	if l.Tail == nil {
		l.Tail = n
	}
	l.Head = n
}
func (l *LinkedList) InsertAtHeadN(data interface{}) {
	n := NewNode(data, l.Head)
	if l.Tail == nil {
		l.Tail = n
	}
	l.Head = n
}

func (l *LinkedList) InsertAtTail(data interface{}) {
	n := NewNode(data, nil)
	if l.Head == nil {
		l.Head = n
	} else {
		l.Tail.Next = n
		//加入尾指针、不需要遍历获取尾指针
		//node := l.Head
		//for node.Next != nil {
		//	node = node.Next
		//}
		//node.Next = n
	}
	l.Tail = n
}

func (l *LinkedList) InsertAtTailN1(data interface{}) {
	n := NewNode(data, nil)
	l.Tail.Next = n
	l.Tail = n
}

func (l *LinkedList) InsertAtTailN(data interface{}) {
	n := NewNode(data, nil)
	if l.Head == nil {
		l.Head = n
	} else {
		l.Tail.Next = n
		//加入尾指针、不需要遍历获取尾指针
		//node := l.Head
		//for node.Next != nil {
		//	node = node.Next
		//}
		//node.Next = n
	}
	l.Tail = n
}

func (l *LinkedList) DeleteIndex(index int) {
	//dummyNode := NewNode(-1, l.Head)
	//prev := dummyNode
	//cur := dummyNode
	//
	//i := -1
	//for cur != nil {
	//	if i == index {
	//		prev.Next = cur.Next
	//		l.Head = prev.Next
	//		return l
	//	}
	//	prev = cur
	//	cur = cur.Next
	//	i++
	//}
	//l.Head = prev.Next
	//return l

	cur := l.Head
	pre := l.Head
	i := 0
	for cur != nil {
		if i == index {
			//如果是头节点 更新头指针
			if index == 0 {
				l.Head = l.Head.Next
				return
			}

			//如果是尾节点 更新尾指针
			if cur.Next == nil {
				l.Tail = pre
			}
			pre.Next = cur.Next
			return
		}
		pre = cur
		cur = cur.Next
		i++
	}
}

func (l *LinkedList) DeleteValue(value interface{}) {
	dummy := NewNode(-1, l.Head)
	prev := dummy
	cur := l.Head

	for cur != nil {
		if cur.Data == value {
			prev.Next = cur.Next
			break
		}
		prev = cur
		cur = cur.Next
	}
}

func (l *LinkedList) DeleteNode(node *Node) {
	cur := l.Head
	pre := l.Head
	for cur != nil {
		if cur == node {
			//如果删除的是头节点 更新头指针
			if node == l.Head {
				l.Head = cur.Next
				return
			}

			//如果删除的是尾节点 更新尾指针
			if cur.Next == nil {
				l.Tail = pre
			}
			pre.Next = cur.Next
			return
		}
		pre = cur
		cur = cur.Next
	}
}

func (l *LinkedList) Traverse() {
	cur := l.Head
	for cur != nil {
		if cur.Next == nil {
			fmt.Printf("%v\n", cur.Data)
		} else {
			fmt.Printf("%v-", cur.Data)
		}
		cur = cur.Next
	}
}

func (l *LinkedList) GetNode(index int) *Node {
	cur := l.Head
	i := 0
	for cur != nil {
		if i == index {
			return cur
		}
		cur = cur.Next
		i++
	}
	return nil
}

func main() {
	var l LinkedList
	//l := NewLinkedList()
	l.InsertAtTailN(3)
	l.InsertAtHead(1)
	l.InsertAtHead(2)
	l.InsertAtHead(4)
	l.InsertAtTail(5)
	l.Traverse()
	l.DeleteIndex(4)
	fmt.Println(l.Tail, l.Head)
	//l.DeleteValue(4)
	l.Traverse()

	node := l.GetNode(0)
	l.DeleteNode(node)
	l.Traverse()

}
